At present, in many distributed computing environments. e.g., cloud computing, grid computing, a P2P network, etc., a request task needs to be scheduled and executed among a plurality of selectable nodes. Existing types of scheduling are based upon multi-task scheduling, workflow scheduling, etc.
Multi-task scheduling refers to that a number of concurrent tasks arrive at a cloud distributed computing environment together, where they need to be scheduled, and resources need to be allocated for them, thus requirement of load balancing of respective execution nodes can be met. Min-Min algorithm and Max-Min algorithm are commonly applied. In the Min-Min algorithm, firstly the minimum completion time for each task in the current task queue on respective processors is predicated, and then the task with the minimum completion time is allocated to a corresponding processor, and also a ready time of the corresponding processor is updated, and the allocated task is removed from the task queue; and this process is repeated to allocate the remaining tasks until the entire task queue is empty. The Min-Min algorithm tends to suffer from load unbalancing. A difference of the Max-Min algorithm from the Min-Min algorithm lies in that after the earliest completion time for each task on the respective processors is determined, the task with the maximum earliest completion time is allocated to a corresponding processor, a ready time of the corresponding processor is updated in a timely manner, and this process is repeated for the remaining tasks. The Max-Min algorithm is improved over the Min-Min algorithm in terms of load balancing.
Another type of scheduling relates to an algorithm of scheduling multiple levels of timing-related sub-tasks in some workflow so as to meet the requirements of shortening a total execution time and a total amount of consumed energy, etc. EDTS algorithm relates to optimum scheduling of N sub-tasks in a task, and in this algorithm, firstly the time and the amount of consumed energy for the respective sub-tasks executed on all the machines are predicated, and then a total length of time is set for this series of sub-tasks, and given the total length of time together with an existing timing relationship, a sub-task allocation manner which consumes energy as low as possible is found, where the task is decomposed and scheduled for optimum performance thereof.
In most of the solutions above, the computing and resources allocation of scheduling scheme are performed by a central server, however, centralized computing may not be practicable in a large-scale distributed network, e.g., a large-scale computing cluster, a P2P network, or another distributed computing environment because it is difficult for the efficiency and the computing overhead thereof to meet the requirements of real-time, quasi-real-time, and other applications.